package tree;

import java.io.IOException;
import java.util.Stack;

import util.Util;

public class BinaryTree {

	public static void main(String[] args) throws Exception 
	{
		InOrderIter();
		PreOrderIter();
		PostOrderIter();
	}

	public static void PostOrderIter() throws Exception
	{
		Node root = serializeIntoTree();
		PostOrderIter(root);
		System.out.println();
	}	
	private static void PostOrderIter(Node<Integer> curNode) throws Exception
	{
		if(curNode == null)
			return;
		Node<Integer> prevNode = null;
		Stack<Node<Integer>> s = new Stack<Node<Integer>>();
		s.push(curNode);
		while(!s.isEmpty())
		{
			curNode = s.peek();

			// DOWN: add all left child to stack, then add a right child, repeat. This is DEPTH.
			// constraint: curNode is a child of prevNode
			if(prevNode == null || prevNode.left == curNode || prevNode.right == curNode)
			{
				if(curNode.left != null)
					s.push(curNode.left);
				else if (curNode.right != null)
					s.push(curNode.right);
			}
			// UP: when just visited curNode's left child, check if we need to visit its right child, This is BREATH
			else if(curNode.left == prevNode)
			{
				if(curNode.right != null)
					s.push(curNode.right);
			}
			else
			{
				visit(curNode);
				s.pop();
			}
			prevNode = curNode;
		}
	}


	public static void InOrderIter() throws Exception
	{
		Node root = serializeIntoTree();
		InOrderIter(root);
		System.out.println();
	}	
	private static void InOrderIter(Node<Integer> curNode) throws Exception
	{
		Stack<Node<Integer>> s = new Stack<Node<Integer>>();
		while(true)
		{
			while(curNode != null)
			{
				s.push(curNode);
				curNode = curNode.left;
			}

			if(s.empty())
				break;

			Node popNode = s.pop();
			visit(popNode);
			curNode = popNode.right;
		}
	}

	public static void PreOrderIter() throws Exception
	{
		Node root = serializeIntoTree();
		PreOrderIter(root);
		System.out.println();
	}	
	private static void PreOrderIter(Node<Integer> curNode) throws Exception
	{
		Stack<Node<Integer>> s = new Stack<Node<Integer>>();
		while(true)
		{
			while(curNode != null)
			{
				visit(curNode);
				if(curNode.right != null) // not necessary
					s.push(curNode.right);
				curNode = curNode.left;
			}
			if(s.empty())
				break;
			curNode = s.pop();
		}
	}

	private static void visit(Node<Integer> curNode) throws Exception
	{
		System.out.print(curNode.data);
		System.out.print(" ");
		Thread.sleep(1000);
	}

	static int curLeafLevel = -1;
	static boolean isSameLevel = true;
	public static void isAllLeafSameLevel_recur(Node curNode, int level)
	{
		if(curNode == null)
		{
			return;
		}
		// hit leaf
		if(curNode.left == null && curNode.right == null)
		{
			if(curLeafLevel != level)
			{
				if(curLeafLevel == -1){
					curLeafLevel = level;
				}
				else{
					isSameLevel = false;
				}
			}
			System.out.println(curNode.data);
			System.out.println(level);
		}
		isAllLeafSameLevel_recur(curNode.left, level + 1);
		isAllLeafSameLevel_recur(curNode.right, level + 1);
		return;
	}


	public static Node serializeIntoTree() throws IOException {
		String serializedString = Util.readFileIntoString("binaryTreeSerialized.txt").trim();
		System.out.println(serializedString);
		String[] itemArray = serializedString.split(" ");
		Node root = deserializeTree(itemArray);
		System.out.println(serializeTree(root));
		BTreePrinter.printNode(root);
		return root;
	}
	public static int index = 0;
	public static <T> Node<T> deserializeTree(T[] itemArray){
		if(index >= itemArray.length || itemArray[index] == null || itemArray[index].equals("#"))
		{
			index++;
			return null;
		}
		Node<T> curNode = new Node<T>();
		curNode.data = itemArray[index];
		index++;
		curNode.left = deserializeTree(itemArray);
		curNode.right = deserializeTree(itemArray);
		return curNode;
	}
	public static String serializeTree(Node root)
	{
		StringBuilder sb = new StringBuilder();
		serializeTree(root, sb);
		return sb.toString();
	}
	private static void serializeTree(Node curNode, StringBuilder sb)
	{
		if(curNode == null)
		{
			sb.append("# ");
			return;
		}
		sb.append(curNode.data + " ");
		serializeTree(curNode.left, sb);
		serializeTree(curNode.right, sb);
	}

	public static void testEquality()
	{
		String obj1 = new String("xyz");
		String obj2 = new String("xyz");
		// == test for memory location equality, but they are in different obj memory location, so false
		if(obj1 == obj2)
			System.out.println("obj1==obj2 is TRUE");
		else
			System.out.println("obj1==obj2 is FALSE"); 
		// String.equals() is overriden to check content equality, so true
		if(obj1.equals(obj2))
			System.out.println("obj1.equals(obj2) is TRUE"); 
		else
			System.out.println("obj1.equals(obj2) is FALSE");
	}


}
